#ifndef __MALLOCCOMMON_H__
#define __MALLOCCOMMON_H__

#include <iostream>
#include <exception>
#include <mutex>
#include <algorithm>
#include <vector>

#ifdef _WIN32
#include <windows.h>
#else
#include <unistd.h>
#include <sys/mman.h>
#endif

#define PAGE_SHIFT 12 //一页所占位数

#if defined __x86_64__
// x86_64 processors use lower 48 bits in virtual to physical address
// translation with 4-level page tables. The top 16 are thus unused.
// We don't support 5-level page tables yet.
// TODO(b/134686025): Under what operating systems can we increase it safely to
// 17? This lets us use smaller page maps.  On first allocation, a 36-bit page
// map uses only 96 KB instead of the 4.5 MB used by a 52-bit page map.
constexpr int kAddressBits = 48;
#elif defined __powerpc64__ && defined __linux__
// Linux(4.12 and above) on powerpc64 supports 128TB user virtual address space
// by default, and up to 512TB if user space opts in by specifying hint in mmap.
// See comments in arch/powerpc/include/asm/processor.h
// and arch/powerpc/mm/mmap.c.
constexpr int kAddressBits = 49;
#elif defined __aarch64__ && defined __linux__
// According to Documentation/arm64/memory.txt of kernel 3.16,
// AARCH64 kernel supports 48-bit virtual addresses for both user and kernel.
constexpr int kAddressBits = 48;
#elif defined __riscv && defined __linux__
constexpr int kAddressBits = 48;
#else
constexpr int kAddressBits = 8 * sizeof(void*);
#endif

#define PAGEBITS kAddressBits - 12 //页数所占位数


#define FREELISTNUM 184
#define PAGE_NUM 129

static void* systemAlloc(size_t pagesize)
{

#ifdef _WIN32
	void *ptr = VirtualAlloc(0, pagesize, MEM_COMMIT | MEM_RESERVE, PAGE_READWRITE);
#else
	//brk mmap
    void* ptr = sbrk(pagesize);
#endif

    //使用sbrk
    if(ptr == (void*)-1)
    {
        //throw std::bad_alloc();
        return nullptr;
    }
    return ptr;
}

static void systemFree(void* ptr, size_t pagesize)
{
#ifdef _WIN32
	VirtualFree(ptr,0,MEM_RELEASE);
#else
    void* cur_brk = sbrk(0);
    void* expected_brk = (char*)ptr + pagesize;

    //验证是否堆顶指针
    if(cur_brk == expected_brk)
    {
        void* res = sbrk(-pagesize);
        if(res == (void*)-1)
        {
            LOG_ERROR("FFL[%s, %s, %u]回收指针失败,pagesize:%u, ptr:%p", LOG_FFL, pagesize, ptr);
        }
    }
#endif
}

//static void* systemAlloc(size_t size)
//{
//    void* p = mmap(nullptr, size, PROT_WRITE | PROT_READ, MAP_ANONYMOUS | MAP_PRIVATE, -1, 0);
//    if(p == MAP_FAILED)
//    {
//        return nullptr;
//    }
//    return p;
//}
//
//static void systemFreeBig(void* ptr, size_t size)
//{
//    int res = munmap(ptr, size);
//    if(res == -1)
//    {
//        LOG_ERROR("FFL[%s, %s, %u]回收指针失败,pagesize:%u, ptr:%p", LOG_FFL, size, ptr);
//    }
//}


static void*& NextObj(void* p)
{
    //返回前面指针大小
        //取obj前4/8字节的值，保存的是下一个内存的指针
    return *(reinterpret_cast<void**>(p));
}

struct qSpan
{
    qSpan()
    :pageid_(0)
    ,pagenum_(0)
    ,size_(0)
    ,usenum_(0)
    ,prev_(nullptr)
    ,next_(nullptr)
    ,list_(nullptr)
    {}

    size_t pageid_;
    size_t pagenum_;
    size_t size_;
    size_t usenum_;
    qSpan* prev_;
    qSpan* next_;

    void* list_;
};

class spanList
{
public:
    spanList()
    {
        head_ = reinterpret_cast<qSpan*>(systemAlloc(sizeof(qSpan)));
        head_->next_ = head_;
        head_->prev_ = head_;
    }

    qSpan* begin()
    {
        return head_->next_;
    } 

    qSpan* end()
    {
        return head_;
    }

    std::mutex& getMutex()
    {
        return mt_;
    }

    bool empty()
    {
        return head_->next_ == head_;
    }

    qSpan* popFront()
    {
        if(empty())
            return nullptr;
            
        qSpan* sp = head_->next_;
        head_->next_ = sp->next_;
        sp->next_->prev_ = head_;

        return sp;
    }

    void pushFront(qSpan* sp)
    {
        qSpan* next = head_->next_;
        next->prev_ = sp;
        sp->next_ = next;

        head_->next_ = sp;
        sp->prev_ = head_;

    }

    bool erase(qSpan* sp)
    {
        bool ret = false;
        qSpan* it = begin();
        while(it != end())
        {
            if(it == sp)
            {
                qSpan* prev_sp = sp->prev_;
                qSpan* next_sp = sp->next_;
        
                prev_sp->next_ = next_sp;
                next_sp->prev_ = prev_sp;
                ret = true;
                // sp->next_ = nullptr;
                // sp->prev_ = nullptr;
                break;
            }
            it = it->next_;
        }
        return ret;

        // qSpan* prev_sp = sp->prev_;
        // qSpan* next_sp = sp->next_;

        // prev_sp->next_ = next_sp;
        // next_sp->prev_ = prev_sp;

        //return true;
    }

private:
    std::mutex mt_;
    //带头双向链表
    qSpan* head_;
};

class freeList
{
public:
    freeList()
    :head_(nullptr)
    ,num_(0)
    ,max_num_(1)
    {}

    void* pop()
    {
        if(num_ == 0 || head_ == nullptr)
            return nullptr;
        void* res = head_;
        head_ = NextObj(head_);
        if(num_ > 0)
            num_--;
        return res;
    }

    size_t popRange(void*& start, void*& end, size_t num)
    {
        if(num_ == 0 || head_ == nullptr)
            return 0;

        if(num > num_)
            num = num_;

        size_t n = 0;
        start = head_;
        while(head_ && n < num)
        {
            end = head_;
            head_ = NextObj(head_);
            n++;
        }
        if(n == 1)
        {
            std::cout << "popRange: " << head_ << std::endl; 
        }

        if(end)
        {
            NextObj(end) = nullptr;
        }
        num_ -= n;
        return n;
    }

    void push(void* p)
    {
        NextObj(p) = head_;
        head_ = p;
        num_++;
    }

    void pushRange(void* start, void* end, size_t num)
    {
        //头插
        NextObj(end) = head_;
        head_ = start;
        num_ += num;
    }

    size_t getMaxNum()
    {
        return max_num_;
    }

    void setMaxNum(size_t num)
    {
        max_num_ = num;
    }

    size_t getNum()
    {
        return num_;
    }

    ~freeList()
    {}
private:
    //从span中切割的内存块
    void* head_;
    size_t num_;
    size_t max_num_;
};

class sizeClass
{
  	//防止由于对齐数太小导致threadcache哈希桶太大，将哈希桶划分多个区间，每个区间对齐数不同。如下：
	//[1, 128]字节，				对齐数8，	区间个数为[0, 15]		16个
	//[129, 1024]字节，			对齐数16，	区间个数为[16, 71]		56个
	//[1025, 8*1024]字节，		对齐数128，	区间个数为[72, 127]		56个 
	//[8*1024+1, 64*1024]字节，	对齐数1024，	区间个数为[128, 183]		56个
    static size_t index(size_t size, size_t n)
    {
        //（1<<n）为对齐数，size加（对齐数-1），(<<n )除以对齐数得到对应索引
        //减1是因为数组索引从0开始
        //是为了让不是对齐数倍数的会到下一个对齐数倍数，并且正好为对齐数倍数的也不会为下一个倍数。
        // 如果直接除以对齐数，5/8-1为负数，越界了。
        return ((size + ((1 << n) - 1)) >> n) - 1;
    }

    static size_t roundUp(size_t size, size_t n)
    {
        //将size向上取整到对齐数的整数倍
        //size加(对齐数-1)，让不是对齐数倍数的会到下一个对齐数倍数，比如 5不到对齐数8的整数倍
        //&~((1 << n) - 1)， 让后面几位无效，这样就向上取整到对齐数的整数倍了
        //比如：如果8进制~((1 << n) - 1) 二进制为 1111 1111 1111 1111 1111 1111 1111 1000，让后面3位无效，直接向上对齐
        //对齐到16的整数倍，让后4位无效，对齐到128整数倍，让后7位无效。。。。
        return (size + ((1 << n) - 1)) & (~((1 << n) - 1));
    }

public:
    static const int kMaxSize = 64 * 1024;

    //获得在哈希桶索引位置
    static size_t getIndex(size_t size)
    {
        if (size > kMaxSize || size <= 0)
        {
            return -1;
        }

        //哈希桶区间个数
        size_t range_num[] = { 16, 56, 56, 56 };
        //计算出每个区间距离区间起始位置的距离，加上之前的区间个数，就是当前位置
        //size为什么要减去前面区间size大小？
        //因为前面区间对齐数不一样，
        //index函数是求出了这个区间从0开始的索引，所以需要加三个前面区间个数
        if (size <= 128)
        {
            return index(size - 0, 3);
        }
        else if (size <= 1024)
        {
            return index(size - 128, 4) + range_num[0];
        }
        else if (size <= 8192)
        {
            return index(size - 1024, 7) + range_num[1] + range_num[0];
        }
        else if (size <= 65536)
        {
            return index(size - 8192, 10) + range_num[2] + range_num[1] + range_num[0];
        }
        return -1;
    }

    //获得size对应区间向上取整的对齐数整数倍
    static size_t getRoundUp(size_t size)
    {
        if (size <= 128)
        {
            return roundUp(size, 3);
        }
        else if (size <= 1024)
        {
            return roundUp(size, 4);
        }
        else if (size <= 8192)
        {
            return roundUp(size, 7);
        }
        else if (size <= 65536)
        {
            return roundUp(size, 10);
        }
        else 
        {
            return roundUp(size, PAGE_SHIFT);
        }
        return 0;
    }

    static inline size_t SizeMoveNum(size_t size)
    {
        size_t num = kMaxSize / size;
        if(num <= 1)
        {
            num = 2;
        }

        if(num >= 512)
        {
            num = 512;
        }
        return num;
    }

    static inline size_t SizeMovePage(size_t size)
    {
        size_t num = SizeMoveNum(size);
        
        size_t pagenum = static_cast<uintptr_t>(size * num >> PAGE_SHIFT);
        if(pagenum == 0)
            pagenum = 1;

        return pagenum;
    }

};


#endif 
